/*
  最长公共子序列
 【题目描述】
    一个给定序列的子序列是在该序列中删去若干元素后得到的序列。
    确切地说，若给定序列 X = <x1, x2, …, xm>，则另一序列 Z＝ <z1，z2，…，zk>是X的
    子序列是指存在一个严格递增的下标序列 <i1, i2, …, ik>, 使得对于所有j=1, 2, …, k有：Xij = Zj
    例如，序列 Z=<B, C, D, B>是序列 X = <A, B, C, B, D, A, B>的子序列,
         相应的递增下标序列为 <2, 3, 5, 7>。
    给定两个序列 X和Y，当另一序列 Z 既是 X 的子序列又是 Y 的子序列时，称 Z 是序列 X和Y 的公共子序列。
    例如，若 X＝<A, B, C, B, D, A, B>和 Y＝<B, D, C, A, B, A>，
          则序列 <B, C, A> 是 X和Y 的一个公共子序列, 序列 <B, C, B, A>也是 X和Y 的一个公共子序列。
          而且，后者是 X和Y 的一个最长公共子序列．因为 X和Y 没有长度大于4的公共子序列。

    给定两个序列 X＝<x1，x2，…，xm> 和 Y=<y1, y2…．yn>．要求找出 X和Y 的一个最长公共子序列。
 【输入】
    共有两行。每行为一个由大写字母构成的长度不超过1000的字符串，表示序列 X和Y。
 【输出】
    第一行为一个非负整数。表示所求得的最长公共子序列的长度。
    若不存在公共子序列．则输出文件仅有一行输出一个整数0。
 【输入样例】
    ABCBDAB
    BDCABA
 【输出样例】
    4
 【提示】
    1). 最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）
        的区别为：
          子串是串的一个连续的部分，子序列则是从不改变序列的顺序，
          而从序列中去掉任意的元素而获得新的序列；
          也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。
    2). 字符串长度小于等于1000。
*/